package com.problem.queue;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/task-scheduler/
 */
public class LeastInterval {
    //给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。
    // 任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
    //
    //然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
    //
    //你需要计算完成所有任务所需要的最短时间。
    //
    //示例 1：
    //
    //输入: tasks = ["A","A","A","B","B","B"], n = 2
    //输出: 8
    //执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
    //注：
    //
    //任务的总个数为 [1, 10000]。
    //n 的取值范围为 [0, 100]。



    //todo 取不到最优解
    public int leastInterval(char[] tasks, int n) {

        //先完整的遍历一遍，不能执行的先进入等待队列，这样能最大程度的使每个时刻都有任务执行

        //有序的等待队列
        Map<String,Map<String,Object>> map = new LinkedHashMap<>();

        Integer taskNum = tasks.length;
        //总cpu时间
        Integer m = 0;
        boolean f = false;
        while (taskNum>0) {
            boolean ex = false;
            for (int i=0;i<tasks.length;i++) {
                char c = tasks[i];
                if ('a' == c) {
                    continue;
                }

                //wtMap: key:wt v:int 等待时间  k:wtList v:List<Integer> 等待任务的索引队列
                Map<String,Object> wtMap = map.get(String.valueOf(c));
                if (wtMap == null || (Integer)wtMap.get("wt")>=n) {//即将第一次执行或等够了n时间
                    //时间等够了可以执行，并用'a'替换，表示已执行
                    if (wtMap == null) {
                        wtMap = new HashMap<>();
                    }
                    wtMap.put("wt",0);//等待时间0
                    List<Integer> l = null;
                    if (wtMap.get("wtList") == null) {
                        l = new ArrayList<Integer>();
                        wtMap.put("wtList",l);
                    } else {
                        l = (List<Integer>) wtMap.get("wtList");//相同任务等待的队列
                        l.remove((Integer) i);//执行完当前任务，从队列中移除,转为Integer删除i元素,否则会删除索引i处的值
                    }
                    map.put(String.valueOf(c),wtMap);

                    tasks[i] = 'a';
                    taskNum--;
                    ex = true;
                    m++;

                    System.out.println(String.valueOf(c)+m);
                    //执行完后其他等待的任务等待时间+1
                    Map<String, Integer> mmm = xxx(tasks, map, m, n, String.valueOf(c), taskNum);
                    m = mmm.get("m");
                    taskNum = mmm.get("taskNum");
                }else {
                    //当前任务未等到n个cpu时间,不耗时间，继续执行
                    //如果当前索引的任务未进入等待队列，则加入
                    List<Integer> l = (List<Integer>) wtMap.get("wtList");//相同任务等待的队列
                    if (!l.contains(i) && l.add(i));
                }
            }
            f = true;
            //这一轮如果都没任务执行，总cpu时间也要加一，表示等待
            if (!ex) {
                m++;

                System.out.println("等待"+m);
                //其他任务等待时间+1，做递归判断
                Map<String,Integer> mmm =xxx(tasks,map,m,n,null,taskNum);
                m = mmm.get("m");
                taskNum = mmm.get("taskNum");
            }
        }


        System.out.println("结束");
        return m;
    }

    private Map<String,Integer> xxx(char[] tasks,Map<String, Map<String,Object>> map,Integer m,int n,String c,int taskNum) {
        for (Map.Entry<String, Map<String,Object>> entry : map.entrySet()) {
            if (entry.getKey().equals(c)) {
                continue;
            }
            Map<String,Object> wt = entry.getValue();
            int iii = (int) wt.get("wt");
            ++iii;
            wt.put("wt",iii);
            //判断已满时立即执行
            if (iii >= n) {
                List<Integer> idxs = (List<Integer>) wt.get("wtList");
                if (idxs != null && idxs.size() > 0) {
                    c = entry.getKey();
                    tasks[idxs.get(0)] = 'a';
                    idxs.remove(0);
                    wt.put("wt",0);
                    m++;

                    taskNum--;
                    System.out.println(c+m);
//                    lllll.add(c);
                    //其他任务等待时间+1，做递归判断
                    Map<String,Integer> msss = xxx(tasks,map,m,n,c,taskNum);
                    m = msss.get("m");
                    taskNum = msss.get("taskNum");
                } else {

                }
            }
        }
        Map<String,Integer> mmm = new HashMap<>();
        mmm.put("taskNum",taskNum);
        mmm.put("m",m);
        return mmm;
    }

    public int leastInterval1(char[] tasks, int n) {
        if(n==0) return tasks.length;
        //每个任务的个数
        int[] number = new int[26];
        for (int i = 0; i<tasks.length; i++){
            number[tasks[i]-'A']++;
        }
        Arrays.sort(number);
        //取出最大值，和最大值个数
        int max = number[number.length-1];
        int i=number.length-1;
        int max_len =0;
        while(number[i--]==max) max_len++;
        //A->B->X ->A->B->X ->A->B
        //A的个数-1*每一组的数     （n+1）+最大值相同的个数
        return Math.max((max-1)*(n+1)+max_len,tasks.length);
    }

    public static void main(String[] args) {
        //char tasks[] = new char[]{'A','A','A','B','B','B'};
        char tasks[] = new char[]{'B','F','J','J','H','A','D','C','C','D','J','E','B','E','C','H','E','E','G','E','H','I','I','E','H','F','C','G','H','F','E','E','I','D','D','A','E','A','C','E','F','J','E','F','G','J','A','A','A','B','E','J','H','C','A','E','D','A','E','I','H','B','A','C','E','F','J','D','F','I','I','H','J','E','B','H','H','A','J','C','C','D','C','B','C','H','H','I','H','D','C','B','D','C','H','A','F','A','J','D','F','E','H','I','D','A','E','B','H','J','F','D','C','J','J','I','A','I','J','H','A','I','I','G','C','C','H','D','B','B','B','H','I','D','B','C','H','I','I','G','E','D','D','A','E','D','H','C','J','H','C','E','I','F','A','I','E','G','A','E','F','I','B','J','B','J','B','G','A','D','C','B','I','A','C','J','J','J','B','E','E','E','B','E','B','H','B','J','H','F','G','B','B','I','C','D','I','D','D','A','I','D','H','A','J','D','J','D','I','G','F','F','B','G','A','F','I','I','H','C','B','H','H','E','F','A','H','G','F','D','G','F','A','C','F','D','F','C','J','A','D','H','G','D','D','G','C','G','C','I','B','G','E','J','C','G','J','G','E','F','F','I','D','D','E','G','F','A','F','H','D','C','B','E','H','G','H','B','A','D','A','J','A','C','B','G','C','A','J','E','I','G','H','J','A','J','I','D','I','G','B','G','I','A','B','J','B','H','E','G','G','I','G','G','C','J','J','J','H','G','A','G','B','G','I','G','A','D','B','A','E','I','H','E','G','H','J','F','H','I','A','E','A','I','A','D','D','B','D','G','E','C','J','C','C','B','F','F','B','E','A','G','D','I','G','D','J','D','G','I','B','J','J','B','F','D','I','C','I','B','J','B','D','D','A','D','C','G','A','G','C','G','C','E','C','G','A','J','C','E','F','C','C','E','J','D','H','H','F','E','D','G','E','E','I','B','G','A','C','C','E','J','F','H','C','A','G','H','G','A','G','A','D','B','E','F','H','C','C','B','I','F','H','I','C','H','G','G','C','E','A','J','F','F','F','B','D','I','E','I','F','E','F','G','G','A','D','I','A','J','A','H','J','I','H','H','A','B','B','B','I','C','J','C','G','J','G','E','I','H','D','E','H','J','A','G','A','G','A','C','F','C','G','E','G','J','D','H','H','B','J','F','J','J','B','J','D','D','G','B','I','I','H','G','B','I','E','D','H','H','I','B','A','A','A','D','H','J','H','D','J','E','D','G','J','B','B','F','G','J','G','E','G','E','E','F','H','F','J','A','G','I','D','C','H','A','C','F','B','J','E','I','A','G','J','D','I','F','I','J','H','E','D','J','A','E','G','B','B','J','I','J','H','F','D','F','F','A','G','F','F','I','C','H','E','E','G','A','D','F','I','D','D','C','B','G','C','D','G','H','F','D','J','D','B','A','J','J','I','H','F','G','D','J','H','I','H','I','A','A','I','C','B','H','G','I','C','F','E','J','J','F','F','D','F','A','J','H','B','G','A','F','D','G','D','C','F','J','F','G','D','H','J','C','A','E','C','G','J','G','I','C','G','H','G','J','D','D','G','D','F','F','J','B','D','C','E','F','G','D','A','J','H','D','F','C','B','H','C','I','D','C','F','E','C','D','J','D','E','G','C','D','H','J','E','H','I','I','A','C','E','C','I','B','A','B','E','E','H','E','B','H','C','G','B','C','C','D','G','G','A','F','A','B','D','G','F','A','H','G','C','E','D','B','H','D','F','F','G','A','J','H','E','B','C','B','B','B','H','D','F','B','B','C','G','A','C','E','J','H','F','F','D','G','J','D','F','J','G','H','B','D','B','D','D','G','J','H','B','D','F','E','E','G','D','H','B','A','I','E','B','E','B','D','I','C','A','A','E','J','A','B','A','F','C','J','F','F','F','A','I','J','F','H','G','C','F','E','D','C','B','C','G','G','G','A','B','J','J','F','J','G','C','D','B','C','F','H','I','F','D','C','I','J','D','I','G','B','G','I','J','E','H','G','G','J','J','A','E','E','I','G','E','H','F','F','C','A','J','I','I','D','C','E','G','A','A','H','F','A','I','B','H','J','H','B','H','A','A','A','G','I','I','D','F','F','C','H','D','B','J','F','G','E','F','J','A','I','G','J','J','F','F','G','B','B','D','F','E','G','D','D','A','D','D','G','C','C','I','C','H','I','C','E','G','C','E','J','F','G','J','B','I','B','B','C','B','G','A','J','H','C','G','D','E','H','E','H','A','H','I','A','J','C','G','B','G','H','G','H'};
        //char tasks[] = new char[]{'G','J','B','I','B','B','C','B','G','A','J','H','C','G','D','E','H','E','H','A','H','I','A','J','C','G','B','G','H','G','H'};
        //char tasks[] = new char[]{'A','A','A','A','A','A','B','C','D','E','F','G'};
        int n = 36;
        System.out.println(new LeastInterval().leastInterval1(tasks,n));


    }

    //相关信息：char 在java中是2个字节。java采用unicode，2个字节（16位）来表示一个字符。
}
